#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int qa,qb;
int mpow(int n,int k)
{
	int i;
	int t = n;
	for(i = 1; i < k;i++)
	{
		t = t * n;
	}
	return t;
}
void generateBoard(int tr,int tc,int dr,int dc,int size,int** b)
{
	int hs = size / 2;
	if(size == 2)
	{
		if( dr == tr && dc == tc )
		{
			//残缺位置在4格左上角 
			//用3号覆盖
			b[tr][tc+1] = 3;
			b[tr+1][tc] = 3;
			b[tr+1][tc+1] = 3;
		}
		if( dr== tr && dc == tc + 1)
		{
			//残缺位置在4格右上角 
			//用4号覆盖
			b[tr][tc] = 4;
			b[tr+1][tc] = 4;
			b[tr+1][tc+1] = 4;
		}
		if( dr == tr + 1 && dc == tc)
		{
			//残缺位置在4格左下角 
			//用1号覆盖
			b[tr][tc] = 1;
			b[tr][tc+1] = 1;
			b[tr+1][tc+1] = 1;	
		}
		if( dr == tr + 1 && dc == tc +1)
		{
			//残缺位置在4格右下角 
			//用2号覆盖
			b[tr][tc] = 2;
			b[tr][tc+1] = 2;
			b[tr+1][tc] = 2;	
		}
/*
		for(int i = 0;i < 2*size;i++)
		{
			for(int j = 0;j < 2*size;j++)
			{
				printf("%d\t",b[i][j]); 
			}
			puts("");
		}
*/
		//printf("\ntr:%d,tc:%d----------------------\n",tr,tc);
		b[qa][qb] = 0;
		return;
	}
	else
	{
		if(dr < tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第二象限
			b[tr+hs-1][tc+hs] = 3;
			b[tr+hs][tc+hs-1] = 3;
			b[tr+hs][tc+hs] = 3;
	
			generateBoard(tr,tc,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
			
		}
		if(dr < tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第一象限
			b[tr+hs-1][tc+hs-1] = 4;
			b[tr+hs][tc+hs-1] = 4;
			b[tr+hs][tc+hs] = 4;
			generateBoard(tr,tc+hs,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b);
			//generateBoard(tr,tc+hs,dr,dc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs - 1; 
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);

			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
		}
		if(dr >= tr + hs && dc < tc + hs)
		{
			int tdr,tdc;
			//残缺在第三象限
			b[tr+hs-1][tc+hs-1] = 1;
			b[tr+hs-1][tc+hs] = 1;
			b[tr+hs][tc+hs] = 1;
			generateBoard(tr+hs,tc,dr,dc,hs,b);
			
			tdr = tr + hs - 1;
			tdc = tc + hs - 1; 
			generateBoard(tr,tc,tdr,tdc,hs,b);

			tdr = tr + hs - 1;
			tdc = tc + hs; 
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			//generateBoard(tr+hs,tc,dr,dc,hs,b);
			
			tdr = tr + hs;
			tdc = tc + hs; 
			generateBoard(tr+hs,tc+hs,tdr,tdc,hs,b);
		}
		if(dr >= tr + hs && dc >= tc + hs)
		{
			int tdr,tdc;
			//残缺在第四象限
			b[tr+hs-1][tc+hs-1] = 2;
			b[tr+hs-1][tc+hs] = 2;
			b[tr+hs][tc+hs-1] = 2;
			generateBoard(tr+hs,tc+hs,dr,dc,hs,b);
			
			tdr = tr+hs-1;
			tdc = tc+hs-1;
			generateBoard(tr,tc,tdr,tdc,hs,b);
			
			tdr = tr+hs-1;
			tdc = tc+hs;
			generateBoard(tr,tc+hs,tdr,tdc,hs,b);
			
			tdr = tr+hs;
			tdc = tc+hs-1;
			generateBoard(tr+hs,tc,tdr,tdc,hs,b);
			//generateBoard(tr+hs,tc+hs,dr,dc,hs,b);
		}
	} 
}
int main()
{
	//左下残缺 右下残缺 左上残缺 右上残缺
	//1 1      2 2        3      4
	//  1      2        3 3      4 4
	//把基础的四格情况分为四种样式的图形，去图形式的填充
	
	int k;
	printf("输入棋盘2^k×2^k的k值：");
	scanf("%d",&k);
	int size = mpow(2,k);
	//printf("size = %d\n",size);
	
	int *b[size]; //生成棋盘矩阵
	for(int i = 0;i < size;i++)
	{
		b[i] = (int*)malloc(sizeof(int)*size);
	}
	for(int i = 0;i < size;i++)
	{
		for(int j = 0;j < size;j++)
		{
			b[i][j] = -1;
		}
		//puts("");
	}
	
	printf("输入残缺位置（行 列）：");
	scanf("%d %d",&qa,&qb);
	int dr,dc;
	dr = qa;
	dc = qb;
	
	if((qa < size && qa >= 0) && (qb < size && qb >= 0))
	{
		b[qa][qb] = 0;
		generateBoard(0,0,dr,dc,size,b);
		
		for(int i = 0;i < size;i++)
		{
			for(int j = 0;j < size;j++)
			{
				printf("%d  ",b[i][j]); 
			}
			puts("");
		}
	}
	else
	{
		printf("残缺位置不在棋盘上，位置不合法！");
	}
	for(int i = 0;i < size;i++)
	{
		free(b[i]);
	}
	system("pause");
	return 0;
}